﻿#pragma once

#include<iostream>

using namespace std;

enum color
{
	Red,
	Black
};

template<class K, class V>
struct RBTressNode
{
	pair<K, V> _kv;

	RBTressNode<K, V>* _left;
	RBTressNode<K, V>* _right;
	RBTressNode<K, V>* _parent;

	color _color;

	RBTressNode(pair<K, V> kv)
		:_kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
	{}
};

template<class K, class V>
class RBTree
{
	typedef RBTressNode<K, V> Node;

public:

	bool insert(const pair<K, V> kv)
	{
		//正常的搜索二叉树的查找后插入
		if (_root == nullptr) {
			_root = new Node(kv);
			_root->_color = Black;
			return true;
		}
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}
		cur = new Node(kv);
		cur->_color = Red;
		if (parent->_kv.first < kv.first)
			parent->_right = cur;
		else
			parent->_right = cur;
		cur->_parent = parent;

		//////////thinkint......
		//开始调整
		//父亲是红色，出现连续的红色
		while (parent && parent->_color == Red)
		{
			Node* pparent = parent->_parent;

			if (parent == pparent->_left)
			{
				//当uncle在右边的情况
				Node* uncle = pparent->_right;
				if (uncle && uncle->_color == Red)
				{
					parent->_color = uncle->_color = Black;
					pparent->_color = Red;

					cur = pparent;
					parent = cur->_parent;
				}
				else
				{
					//当uncle为null或uncle为黑节点时
					//当为空要判断两种情况：当uncle在右边时
					// 是  pp  或  pp  两种情况       
					//   p   u   p    u                           
					// c           c                       

					if (cur == parent->_left)
					{
						//进行右旋
						RotateR(pparent);
						pparent->_color = Red;
						parent->_color = Black;
					}
					else
					{
						//左右旋
						RotateL(parent);
						RotateR(pparent);

						pparent->_color = Red;
						cur->_color = Black;
					}
					break;
				}
			}
			else
			{

				Node* uncle = pparent->_left;
				if (uncle && uncle->_color == Red)
				{
					parent->_color = uncle->_color = Black;
					pparent->_color = Red;

					cur = pparent;
					parent = cur->_parent;
				}
				else
				{
					//当uncle为null或uncle为黑节点时
					//当为空要判断两种情况：
					//当uncle在左边的时候：
					//     pp          或        pp
					//   u     p               u     p
					//          c                 c                   

					if (cur == parent->_right)
					{
						//进行右旋
						RotateL(pparent);
						pparent->_color = Red;
						parent->_color = Black;
					}
					else
					{
						//右左旋
						RotateR(parent);
						RotateL(pparent);

						pparent->_color = Red;
						cur->_color = Black;
					}
					break;
				}

			}

		}
		//让根节点变成黑的
		_root->_color = Black;
		return true;
	}


	void RotateR(Node* pparent)
	{
		Node* cur = pparent->_left;
		Node* curR = cur->_right;

		Node* ppparent = pparent->_parent;

		pparent->_left = curR;
		cur->_right = pparent;

		if (curR)
			curR->_parent = pparent;
		
		pparent->_parent = cur;
		
		if (ppparent == nullptr)
		{
			_root = cur;
			cur->_parent = nullptr;
		}
		else
		{
			if (ppparent->_left == pparent)
				ppparent->_left = cur;
			else
				ppparent->_right = cur;

			cur->_parent = ppparent;
		}

	}
	//左单旋
	void RotateL(Node* parent)
	{
		Node* cur = parent->_right;
		Node* curL = cur->_left;

		Node* pparent = parent->_parent;

		cur->_left = parent;
		parent->_right = curL;

		if (curL)
			curL->_parent = parent;

		if (pparent == nullptr)
		{
			_root = cur;
			cur->_parent = nullptr;
		}
		else
		{
			if (pparent->_left == parent)
				pparent->_left = cur;
			else
				pparent->_right = cur;

			cur->_parent = pparent;
		}
	}

	bool Check(Node* root, int blackNum, const int refNum)
	{
		if (root == nullptr)
		{
			// 前序遍历⾛到空时，意味着⼀条路径⾛完了
			//cout << blackNum << endl;
			if (refNum != blackNum)
			{
				cout << "存在⿊⾊结点的数量不相等的路径" << endl;
				return false;
			}
			return true;
		}
		// 检查孩⼦不太⽅便，因为孩⼦有两个，且不⼀定存在，反过来检查⽗亲就⽅便多了
		if (root->_color == Red && root->_parent->_color == Red)
		{
			cout << root->_kv.first << "存在连续的红⾊结点" << endl;
			return false;
		}
		if (root->_color == Black)
		{
			blackNum++;
		}
		return Check(root->_left, blackNum, refNum)
			&& Check(root->_right, blackNum, refNum);
	}

	bool IsBalance()
	{
		if (_root == nullptr)
			return true;
		if (_root->_color == Red)
			return false;
		// 参考值
		int refNum = 0;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_color == Black)
			{
				++refNum;
			}
			cur = cur->_left;
		}
		return Check(_root, 0, refNum);
	}

private:
	Node* _root = nullptr;
};
